package com.mlh.binarytree.BFS;

import com.mlh.binarytree.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 缪林辉
 * @date 2024/3/26 10:59
 * @DESCRIPTION
 */
// 给定一个二叉树 root ，返回其最大深度。
// 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
public class 二叉树的最大深度 {
    public int method1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);
        int maxDepth = 0;
        while (!treeNodes.isEmpty()) {
            int len = treeNodes.size();
            maxDepth++;
            while (len > 0) {
                TreeNode node = treeNodes.poll();
                len--;
                if (node.left != null) {
                    treeNodes.add(node.left);
                }
                if (node.right != null) {
                    treeNodes.add(node.right);
                }
            }
        }
        return maxDepth;
    }

    //递归
    public int method2(TreeNode root) {
        return recursion(root);
    }

    public int recursion(TreeNode node){
        if(node==null){
            return 0;
        }
        int leftHeight = recursion(node.left);
        int rightHeight = recursion(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public int practice(TreeNode root){
        if(root==null){
            return 0;
        }
        return recursionPractice(root);
    }

    private int recursionPractice(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(recursionPractice(root.left),recursionPractice(root.right))+1;
    }

    public int practice2(TreeNode root){
        if(root==null){
            return 0;
        }
        return recursionPractice2(root);
    }

    private int recursionPractice2(TreeNode node) {
        if(node==null){
            return 0;
        }
        return Math.max(recursionPractice2(node.left),recursionPractice2(node.right))+1;
    }
}
